/*
 * (C) Copyright 2014-2016, by Dimitrios Michail
 *
 * JHeaps Library
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jheaps.tree

import org.jheaps.DoubleEndedHeap
import org.junit.Assert
import org.junit.Test
import java.util.*
import kotlin.random.Random

abstract class AbstractDoubleEndedHeapTest : AbstractComparatorLongHeapTest() {
    abstract override fun createHeap(): DoubleEndedHeap<Long>

    abstract override fun createHeap(capacity: Int): DoubleEndedHeap<Long>

    abstract override fun createHeap(comparator: Comparator<Long?>?): DoubleEndedHeap<Long>

    @Test
    fun testInsertDeleteMax() {
        val h = createHeap()

        for (i in 0 until SIZE) {
            h.insert(i.toLong())
            Assert.assertEquals(0, h.findMin())
            Assert.assertEquals(i.toLong(), h.findMax())
            Assert.assertFalse(h.isEmpty)
            Assert.assertEquals(h.size(), (i + 1).toLong())
        }

        for (i in SIZE - 1 downTo 0) {
            Assert.assertEquals(h.findMin(), 0)
            Assert.assertEquals(h.findMax(), i.toLong())
            h.deleteMax()
        }
    }

    @Test(expected = NoSuchElementException::class)
    fun testBadDeleteMax() {
        val h = createHeap()
        h.deleteMax()
    }

    @Test(expected = NoSuchElementException::class)
    fun testBadFindMax() {
        val h = createHeap()
        h.findMax()
    }

    @Test
    fun testSortMaxRandom() {
        testSort(SIZE, Random(1))
        testSortReverse(SIZE, Random(1))
        testSort(SIZE, Random(2))
        testSortReverse(SIZE, Random(2))
        testSort(SIZE, Random(3))
        testSortReverse(SIZE, Random(3))
        testSort(SIZE, Random(4))
        testSortReverse(SIZE, Random(4))
        testSort(SIZE, Random(5))
        testSortReverse(SIZE, Random(5))
        testSort(SIZE, Random(6))
        testSortReverse(SIZE, Random(6))
    }

    @Test
    fun testSmallInstanceSortMaxRandom() {
        for (seed in 13..999) {
            testSort(SIZE / 100, Random(seed))
            testSortReverse(SIZE / 100, Random(seed))
        }
    }

    @Test
    fun testFindMaxDeleteMaxSameObject() {
        val h = createHeap()

        val generator = Random(1)

        for (i in 0 until SIZE) {
            h.insert(generator.nextLong())
        }

        while (!h.isEmpty) {
            Assert.assertEquals(h.findMax(), h.deleteMax())
        }
    }

    @Test
    fun testWithComparatorMax() {
        val h = createHeap(comparator)

        var i: Long = 0
        while (i < SIZE) {
            h.insert(i)
            Assert.assertEquals(i, h.findMin())
            Assert.assertEquals(0, h.findMax())
            Assert.assertFalse(h.isEmpty)
            Assert.assertEquals(h.size(), i + 1)
            i++
        }

        i = (SIZE - 1).toLong()
        while (i >= 0) {
            Assert.assertEquals(h.findMin(), i)
            Assert.assertEquals(h.findMax(), 0)
            h.deleteMin()
            i--
        }
    }

    @Test
    fun test3Elements() {
        val h = createHeap()

        Assert.assertTrue(h.isEmpty)

        h.insert(780L)
        h.insert(800L)
        h.insert(900L)

        Assert.assertEquals(h.size(), 3)

        Assert.assertEquals(780, h.findMin())
        Assert.assertEquals(900, h.findMax())
    }

    @Test
    fun test3Elements1() {
        val h = createHeap()

        Assert.assertTrue(h.isEmpty)

        h.insert(900L)
        h.insert(800L)
        h.insert(780L)

        Assert.assertEquals(h.size(), 3)

        Assert.assertEquals(780, h.findMin())
        Assert.assertEquals(900, h.findMax())
        Assert.assertEquals(900, h.deleteMax())
    }

    @Test
    fun test3ElementsComparator() {
        val h = createHeap(comparator)

        Assert.assertTrue(h.isEmpty)

        h.insert(900L)
        h.insert(800L)
        h.insert(780L)

        Assert.assertEquals(h.size(), 3)

        Assert.assertEquals(780, h.findMax())
        Assert.assertEquals(900, h.findMin())
    }

    @Test
    fun test3ElementsComparator1() {
        val h = createHeap(comparator)

        Assert.assertTrue(h.isEmpty)

        h.insert(900L)
        h.insert(800L)
        h.insert(780L)
        h.insert(850L)

        Assert.assertEquals(h.size(), 4)

        Assert.assertEquals(780, h.findMax())
        Assert.assertEquals(900, h.findMin())
        Assert.assertEquals(780, h.deleteMax())
    }

    @Test
    fun testOnly4ReverseMax() {
        val h = createHeap(comparator)

        Assert.assertTrue(h.isEmpty)

        h.insert(780L)
        Assert.assertEquals(h.size(), 1)
        Assert.assertEquals(780, h.findMin())
        Assert.assertEquals(780, h.findMax())

        h.insert(-389L)
        Assert.assertEquals(h.size(), 2)
        Assert.assertEquals(780, h.findMin())
        Assert.assertEquals(-389, h.findMax())

        h.insert(306L)
        Assert.assertEquals(h.size(), 3)
        Assert.assertEquals(780, h.findMin())
        Assert.assertEquals(-389, h.findMax())

        h.insert(579L)
        Assert.assertEquals(h.size(), 4)
        Assert.assertEquals(780, h.findMin())
        Assert.assertEquals(-389, h.findMax())

        h.deleteMin()
        Assert.assertEquals(h.size(), 3)
        Assert.assertEquals(579, h.findMin())
        Assert.assertEquals(-389, h.findMax())

        h.deleteMax()
        Assert.assertEquals(h.size(), 2)
        Assert.assertEquals(579, h.findMin())
        Assert.assertEquals(306, h.findMax())

        h.deleteMin()
        Assert.assertEquals(h.size(), 1)
        Assert.assertEquals(306, h.findMin())

        h.deleteMax()
        Assert.assertEquals(h.size(), 0)

        Assert.assertTrue(h.isEmpty)
    }

    private fun testSort(size: Int, rng: Random) {
        val h = createHeap()

        for (i in 0 until size) {
            h.insert(rng.nextLong())
        }

        var prev: Long? = null
        var cur: Long
        while (!h.isEmpty) {
            cur = h.deleteMax()
            if (prev != null) {
                Assert.assertTrue(prev.compareTo(cur) >= 0)
            }
            prev = cur
        }
    }

    private fun testSortReverse(size: Int, rng: Random) {
        val h = createHeap(comparator)

        for (i in 0 until size) {
            h.insert(rng.nextLong())
        }

        var prev: Long? = null
        var cur: Long
        while (!h.isEmpty) {
            cur = h.deleteMax()
            if (prev != null) {
                Assert.assertTrue(comparator!!.compare(prev, cur) >= 0)
            }
            prev = cur
        }
    }
}
